// Copyright (c) 2013 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "content/browser/indexed_db/leveldb/leveldb_transaction.h"

#include "base/logging.h"
#include "base/memory/ptr_util.h"
#include "base/metrics/histogram_macros.h"
#include "base/time/time.h"
#include "content/browser/indexed_db/indexed_db_tracing.h"
#include "content/browser/indexed_db/leveldb/leveldb_database.h"
#include "content/browser/indexed_db/leveldb/leveldb_write_batch.h"
#include "third_party/leveldatabase/src/include/leveldb/db.h"

using base::StringPiece;

namespace content {

LevelDBTransaction::LevelDBTransaction(LevelDBDatabase* db)
    : db_(db)
    , snapshot_(db)
    , comparator_(db->Comparator())
    , data_comparator_(comparator_)
    , data_(data_comparator_)
    , finished_(false)
{
}

LevelDBTransaction::Record::Record()
    : deleted(false)
{
}
LevelDBTransaction::Record::~Record() { }

LevelDBTransaction::~LevelDBTransaction() { }

bool LevelDBTransaction::Set(const StringPiece& key,
    std::string* value,
    bool deleted)
{
    DCHECK(!finished_);
    DataType::iterator it = data_.find(key);

    if (it == data_.end()) {
        std::unique_ptr<Record> record = base::MakeUnique<Record>();
        record->key.assign(key.begin(), key.end() - key.begin());
        record->value.swap(*value);
        record->deleted = deleted;
        data_[record->key] = std::move(record);
        NotifyIterators();
        return false;
    }
    bool replaced_deleted_value = it->second->deleted;
    it->second->value.swap(*value);
    it->second->deleted = deleted;
    return replaced_deleted_value;
}

void LevelDBTransaction::Put(const StringPiece& key, std::string* value)
{
    Set(key, value, false);
}

bool LevelDBTransaction::Remove(const StringPiece& key)
{
    std::string empty;
    return !Set(key, &empty, true);
}

leveldb::Status LevelDBTransaction::Get(const StringPiece& key,
    std::string* value,
    bool* found)
{
    *found = false;
    DCHECK(!finished_);
    std::string string_key(key.begin(), key.end() - key.begin());
    DataType::const_iterator it = data_.find(string_key);

    if (it != data_.end()) {
        if (it->second->deleted)
            return leveldb::Status::OK();

        *value = it->second->value;
        *found = true;
        return leveldb::Status::OK();
    }

    leveldb::Status s = db_->Get(key, value, found, &snapshot_);
    if (!s.ok())
        DCHECK(!*found);
    return s;
}

leveldb::Status LevelDBTransaction::Commit()
{
    DCHECK(!finished_);
    IDB_TRACE("LevelDBTransaction::Commit");

    if (data_.empty()) {
        finished_ = true;
        return leveldb::Status::OK();
    }

    base::TimeTicks begin_time = base::TimeTicks::Now();
    std::unique_ptr<LevelDBWriteBatch> write_batch = LevelDBWriteBatch::Create();

    auto it = data_.begin();
    while (it != data_.end()) {
        if (!it->second->deleted)
            write_batch->Put(it->first, it->second->value);
        else
            write_batch->Remove(it->first);
        data_.erase(it++);
    }

    DCHECK(data_.empty());

    leveldb::Status s = db_->Write(*write_batch);
    if (s.ok()) {
        finished_ = true;
        UMA_HISTOGRAM_TIMES("WebCore.IndexedDB.LevelDB.Transaction.CommitTime",
            base::TimeTicks::Now() - begin_time);
    }
    return s;
}

void LevelDBTransaction::Rollback()
{
    DCHECK(!finished_);
    finished_ = true;
    data_.clear();
}

std::unique_ptr<LevelDBIterator> LevelDBTransaction::CreateIterator()
{
    return TransactionIterator::Create(this);
}

std::unique_ptr<LevelDBTransaction::DataIterator>
LevelDBTransaction::DataIterator::Create(LevelDBTransaction* transaction)
{
    return base::WrapUnique(new DataIterator(transaction));
}

bool LevelDBTransaction::DataIterator::IsValid() const
{
    return iterator_ != data_->end();
}

leveldb::Status LevelDBTransaction::DataIterator::SeekToLast()
{
    iterator_ = data_->end();
    if (iterator_ != data_->begin())
        --iterator_;
    return leveldb::Status::OK();
}

leveldb::Status LevelDBTransaction::DataIterator::Seek(
    const StringPiece& target)
{
    iterator_ = data_->lower_bound(target);
    return leveldb::Status::OK();
}

leveldb::Status LevelDBTransaction::DataIterator::Next()
{
    DCHECK(IsValid());
    ++iterator_;
    return leveldb::Status::OK();
}

leveldb::Status LevelDBTransaction::DataIterator::Prev()
{
    DCHECK(IsValid());
    if (iterator_ != data_->begin())
        --iterator_;
    else
        iterator_ = data_->end();
    return leveldb::Status::OK();
}

StringPiece LevelDBTransaction::DataIterator::Key() const
{
    DCHECK(IsValid());
    return iterator_->first;
}

StringPiece LevelDBTransaction::DataIterator::Value() const
{
    DCHECK(IsValid());
    DCHECK(!IsDeleted());
    return iterator_->second->value;
}

bool LevelDBTransaction::DataIterator::IsDeleted() const
{
    DCHECK(IsValid());
    return iterator_->second->deleted;
}

LevelDBTransaction::DataIterator::~DataIterator() { }

LevelDBTransaction::DataIterator::DataIterator(LevelDBTransaction* transaction)
    : data_(&transaction->data_)
    , iterator_(data_->end())
{
}

std::unique_ptr<LevelDBTransaction::TransactionIterator>
LevelDBTransaction::TransactionIterator::Create(
    scoped_refptr<LevelDBTransaction> transaction)
{
    return base::WrapUnique(new TransactionIterator(transaction));
}

LevelDBTransaction::TransactionIterator::TransactionIterator(
    scoped_refptr<LevelDBTransaction> transaction)
    : transaction_(transaction)
    , comparator_(transaction_->comparator_)
    , data_iterator_(DataIterator::Create(transaction_.get()))
    , db_iterator_(transaction_->db_->CreateIterator(&transaction_->snapshot_))
    , current_(0)
    , direction_(FORWARD)
    , data_changed_(false)
{
    transaction_->RegisterIterator(this);
}

LevelDBTransaction::TransactionIterator::~TransactionIterator()
{
    transaction_->UnregisterIterator(this);
}

bool LevelDBTransaction::TransactionIterator::IsValid() const
{
    return !!current_;
}

leveldb::Status LevelDBTransaction::TransactionIterator::SeekToLast()
{
    leveldb::Status s = data_iterator_->SeekToLast();
    DCHECK(s.ok());
    s = db_iterator_->SeekToLast();
    if (!s.ok())
        return s;
    direction_ = REVERSE;

    HandleConflictsAndDeletes();
    SetCurrentIteratorToLargestKey();
    return s;
}

leveldb::Status LevelDBTransaction::TransactionIterator::Seek(
    const StringPiece& target)
{
    leveldb::Status s = data_iterator_->Seek(target);
    DCHECK(s.ok());
    s = db_iterator_->Seek(target);
    if (!s.ok())
        return s;
    direction_ = FORWARD;

    HandleConflictsAndDeletes();
    SetCurrentIteratorToSmallestKey();
    return s;
}

leveldb::Status LevelDBTransaction::TransactionIterator::Next()
{
    DCHECK(IsValid());
    if (data_changed_)
        RefreshDataIterator();

    leveldb::Status s;
    if (direction_ != FORWARD) {
        // Ensure the non-current iterator is positioned after Key().

        LevelDBIterator* non_current = (current_ == db_iterator_.get())
            ? data_iterator_.get()
            : db_iterator_.get();

        non_current->Seek(Key());
        if (non_current->IsValid() && !comparator_->Compare(non_current->Key(), Key())) {
            // Take an extra step so the non-current key is
            // strictly greater than Key().
            s = non_current->Next();
            if (!s.ok())
                return s;
        }
        DCHECK(!non_current->IsValid() || comparator_->Compare(non_current->Key(), Key()) > 0);

        direction_ = FORWARD;
    }

    s = current_->Next();
    if (!s.ok())
        return s;
    HandleConflictsAndDeletes();
    SetCurrentIteratorToSmallestKey();
    return leveldb::Status::OK();
}

leveldb::Status LevelDBTransaction::TransactionIterator::Prev()
{
    DCHECK(IsValid());
    leveldb::Status s;
    if (data_changed_)
        RefreshDataIterator();

    if (direction_ != REVERSE) {
        // Ensure the non-current iterator is positioned before Key().

        LevelDBIterator* non_current = (current_ == db_iterator_.get())
            ? data_iterator_.get()
            : db_iterator_.get();

        s = non_current->Seek(Key());
        if (!s.ok())
            return s;
        if (non_current->IsValid()) {
            // Iterator is at first entry >= Key().
            // Step back once to entry < key.
            // This is why we don't check for the keys being the same before
            // stepping, like we do in Next() above.
            non_current->Prev();
        } else {
            // Iterator has no entries >= Key(). Position at last entry.
            non_current->SeekToLast();
        }
        DCHECK(!non_current->IsValid() || comparator_->Compare(non_current->Key(), Key()) < 0);

        direction_ = REVERSE;
    }

    s = current_->Prev();
    if (!s.ok())
        return s;
    HandleConflictsAndDeletes();
    SetCurrentIteratorToLargestKey();
    return leveldb::Status::OK();
}

StringPiece LevelDBTransaction::TransactionIterator::Key() const
{
    DCHECK(IsValid());
    if (data_changed_)
        RefreshDataIterator();
    return current_->Key();
}

StringPiece LevelDBTransaction::TransactionIterator::Value() const
{
    DCHECK(IsValid());
    if (data_changed_)
        RefreshDataIterator();
    return current_->Value();
}

void LevelDBTransaction::TransactionIterator::DataChanged()
{
    data_changed_ = true;
}

void LevelDBTransaction::TransactionIterator::RefreshDataIterator() const
{
    DCHECK(data_changed_);

    data_changed_ = false;

    if (data_iterator_->IsValid() && data_iterator_.get() == current_) {
        return;
    }

    if (db_iterator_->IsValid()) {
        // There could be new records in data that we should iterate over.

        if (direction_ == FORWARD) {
            // Try to seek data iterator to something greater than the db iterator.
            data_iterator_->Seek(db_iterator_->Key());
            if (data_iterator_->IsValid() && !comparator_->Compare(data_iterator_->Key(), db_iterator_->Key())) {
                // If equal, take another step so the data iterator is strictly greater.
                data_iterator_->Next();
            }
        } else {
            // If going backward, seek to a key less than the db iterator.
            DCHECK_EQ(REVERSE, direction_);
            data_iterator_->Seek(db_iterator_->Key());
            if (data_iterator_->IsValid())
                data_iterator_->Prev();
        }
    }
}

bool LevelDBTransaction::TransactionIterator::DataIteratorIsLower() const
{
    return comparator_->Compare(data_iterator_->Key(), db_iterator_->Key()) < 0;
}

bool LevelDBTransaction::TransactionIterator::DataIteratorIsHigher() const
{
    return comparator_->Compare(data_iterator_->Key(), db_iterator_->Key()) > 0;
}

void LevelDBTransaction::TransactionIterator::HandleConflictsAndDeletes()
{
    bool loop = true;

    while (loop) {
        loop = false;

        if (data_iterator_->IsValid() && db_iterator_->IsValid() && !comparator_->Compare(data_iterator_->Key(), db_iterator_->Key())) {
            // For equal keys, the data iterator takes precedence, so move the
            // database iterator another step.
            if (direction_ == FORWARD)
                db_iterator_->Next();
            else
                db_iterator_->Prev();
        }

        // Skip over delete markers in the data iterator until it catches up with
        // the db iterator.
        if (data_iterator_->IsValid() && data_iterator_->IsDeleted()) {
            if (direction_ == FORWARD && (!db_iterator_->IsValid() || DataIteratorIsLower())) {
                data_iterator_->Next();
                loop = true;
            } else if (direction_ == REVERSE && (!db_iterator_->IsValid() || DataIteratorIsHigher())) {
                data_iterator_->Prev();
                loop = true;
            }
        }
    }
}

void LevelDBTransaction::TransactionIterator::SetCurrentIteratorToSmallestKey()
{
    LevelDBIterator* smallest = 0;

    if (data_iterator_->IsValid())
        smallest = data_iterator_.get();

    if (db_iterator_->IsValid()) {
        if (!smallest || comparator_->Compare(db_iterator_->Key(), smallest->Key()) < 0)
            smallest = db_iterator_.get();
    }

    current_ = smallest;
}

void LevelDBTransaction::TransactionIterator::SetCurrentIteratorToLargestKey()
{
    LevelDBIterator* largest = 0;

    if (data_iterator_->IsValid())
        largest = data_iterator_.get();

    if (db_iterator_->IsValid()) {
        if (!largest || comparator_->Compare(db_iterator_->Key(), largest->Key()) > 0)
            largest = db_iterator_.get();
    }

    current_ = largest;
}

void LevelDBTransaction::RegisterIterator(TransactionIterator* iterator)
{
    DCHECK(iterators_.find(iterator) == iterators_.end());
    iterators_.insert(iterator);
}

void LevelDBTransaction::UnregisterIterator(TransactionIterator* iterator)
{
    DCHECK(iterators_.find(iterator) != iterators_.end());
    iterators_.erase(iterator);
}

void LevelDBTransaction::NotifyIterators()
{
    for (auto* transaction_iterator : iterators_)
        transaction_iterator->DataChanged();
}

std::unique_ptr<LevelDBDirectTransaction> LevelDBDirectTransaction::Create(
    LevelDBDatabase* db)
{
    return base::WrapUnique(new LevelDBDirectTransaction(db));
}

LevelDBDirectTransaction::LevelDBDirectTransaction(LevelDBDatabase* db)
    : db_(db)
    , write_batch_(LevelDBWriteBatch::Create())
    , finished_(false)
{
}

LevelDBDirectTransaction::~LevelDBDirectTransaction()
{
    write_batch_->Clear();
}

void LevelDBDirectTransaction::Put(const StringPiece& key,
    const std::string* value)
{
    DCHECK(!finished_);
    write_batch_->Put(key, *value);
}

leveldb::Status LevelDBDirectTransaction::Get(const StringPiece& key,
    std::string* value,
    bool* found)
{
    *found = false;
    DCHECK(!finished_);

    leveldb::Status s = db_->Get(key, value, found);
    DCHECK(s.ok() || !*found);
    return s;
}

void LevelDBDirectTransaction::Remove(const StringPiece& key)
{
    DCHECK(!finished_);
    write_batch_->Remove(key);
}

leveldb::Status LevelDBDirectTransaction::Commit()
{
    DCHECK(!finished_);
    IDB_TRACE("LevelDBDirectTransaction::Commit");

    leveldb::Status s = db_->Write(*write_batch_);
    if (s.ok()) {
        finished_ = true;
        write_batch_->Clear();
    }
    return s;
}

} // namespace content
